There are several categories of prior art patents that apply to the present invention. These patents involve mainly mobile robots and groups of mobile robots.
Matsuda (robot system and control device), U.S. Pat. No. 5,825,981; Peless et al. (method for operating a robot), U.S. patent application publication No. 20010047231; and Nourbakhsh et al. (socially interactive autonomous robot), U.S. patent application publication No. 20020013641, mobile robots are used automatically, or with manual intervention to perform tasks such as multifunctional manufacturing, cleaning, mowing, snow blowing or interacting with humans. These pedestrian approaches to robotic control fit into the main paradigm of robotic applications.
Kawakami (mobile robot control system), U.S. Pat. No. 5,652,489; Asama et al., (mobile robot sensor system), U.S. Pat. No. 5,819,008; and Wallach et al. (autonomous multi-platform robot system), U.S. Pat. No. 6,374,155 involve multiple mobile robots. These patents involve using sensors for navigation and obstacle avoidance. In addition, one mobile robot can transmit information to another mobile robot for some effect. These inventions offer only rudimentary connections between robots and lack advanced system functions.
Most of the research history involving the technologies of the present system—including (1) intelligent agents and self-organizing systems, (2) AI and D-AI in coordinated systems, (3) negotiation and problem solving and (4) cooperating agents and aggregation—are represented in the academic literature, described below.
The development of complexity theory is fairly recent. Theorists from economics and biology advanced the view in the 1980s that systems are self-organizing and adaptive of their environments. In particular, biologists have studied ant and insect social organization and have observed the complex adaptive behaviors of these societies.
Researchers at the Sante Fe Institute (SFI) have developed complexity theory by looking at the fields of biology, economics, mathematics, epistemology and computer science. One of the aims of the SFI is to develop a complex self-organizing computer model representing artificial autonomous agents that emulate the biological functions of complex insect social behavior.
SFI theorists have developed the swarm intelligence model of artificial computer societies primarily for simulating economic systems. The swarm intelligence model, by emulating biological system operation, uses ideas of emergent behavior to describe the complex social interactions of relatively simple insects according to straightforward decentralized rules governing group activity.
The challenge for computer scientists lies in how to develop a system of self-organized autonomous robotic agents. The development of societies of behavior-based robotics that fuse elements of system control with elements of decentralized local control is one of the most difficult challenges in computer science and robotics. A key part of this problem lies in how to configure AI systems for problem solving in a MRS for collective behavior. In short, how can we design an intelligent MRS for optimal adaptation to dynamic environments?
The computer science fields of robotics and AI have evolved in the past decade in such a way that a convergence of technologies allows an explosion in research in collective robotics and in intelligent systems in order to achieve the goals of developing an intelligent MRS for group behavior. For example, rapid advances in computation resources, communications and networking allow the combination of integrated technologies necessary for a development of a sophisticated MRS. In addition, in the area of AI research, several trends have emerged, including GA, GP, A-NN and distributed AI, that allow computer systems to not only learn but achieve some degree of autonomy.
In the early 90s, Brooks developed a decentralized modular approach to robotics at MIT's Media Lab. Revolutionary at the time because it spurned conventional wisdom of highly computation-intensive deliberative robotic control approaches, his modular approach used less than three percent of traditional computer approaches. This leap in efficiency was achieved by separating the subsystems for automatic reactive control (he called it subsumption) rather than deliberative top-down robot system control. The mobility, navigation and pick-up functions of the robot could be separated for increased efficiency.
By exploiting this research stream, Arkin (1998) developed a behavior-based model of robotics. In this model, Arkin describes behavior-based robotic architectures as well as experiments in the field with sophisticated hybrid robotic architectures. An example of this hybrid approach is NASA's Atlantis system (1991) that synthesizes deliberative planning with group behavior. The aim of these models is to develop autonomous robots that are adaptive to their environment. The development of robotic teams with social behavior is one of the most difficult challenges, according to Arkin's pioneer study.
Bonabeau et al. (1999), an SFI fellow, develops a research stream that connects the study of ant and insect behavior in complex biological social systems with the development of complex artificial robotic societies. In their vision of swarm intelligence, they use key notions of system self-organization, reactive behavior and environmental adaptation to point to a model for artificial robotic systems that might emulate biological systems.
In 2001, Kennedy and Eberhart focused on the social and theoretical aspects of swarm intelligence. Their examination of group behavior develops a computer model of adaptive self-organized systems, similar to economic “particle” simulations by the SFI, by emulating the social behavior of biological systems. In order to develop an artificial swarm system, the authors look to complex pattern emergence, which has a lineage from Von Neumann to Burks to Wolfram. In this research stream, cellular automata are used to simulate a complex but stable self-organizing system. Though the authors refer to research experiments with robot societies, their focus remains on computer and theoretical models of complex social behavior involving autonomous entities.
Another important research stream involves the application of AI to networks. The emergence of the Internet has presented novel ways to conduct commerce automatically with autonomous software agents in a MAS. Originally developed by Smith, the contract-net protocol established an early model for distributed problem solving. As the Internet evolved rapidly, new computational systems emerged to emulate commercial systems. Solomon has developed demand-initiated self-organizing commercial systems for both intermediated and dis-intermediated transactions that employ novel multivariate and multilateral negotiation models.
One niche of the automated commerce system lies in the aggregation of autonomous agents. Precisely how to combine pools of autonomous agents for wholesale discounts presents an opportunity to remove a layer of distribution from commercial systems. This research stream is important because it provides clues as to how to develop coalitions of robotic agents for common purposes.
MRS models have been developed. The Nerd Herd is an example of an MRS using rule-based social behaviors for subsumption based foraging popularized by Brooks. Second, the Alliance architecture developed a modular approach to robot team behavior that includes inter-robot communication. Such communication allows for emergent cooperation. An additional version of Alliance (L-Alliance) accommodates the learning aspect of robotic agents in order to achieve a form of adaptation.
Arkin developed a “multiagent schema-based robotic architecture” in which team cooperation was modeled using a behavior-based approach without explicit inter-robot communication.
Dias and Stentz provide a market-based model for multirobotic coordination in which individual robots in a distributed environment negotiate with each other in order to agree upon a course of action. Such a model applies the contract-net protocol used with software agents in a distributed network to the robotics context for operation of groups of autonomous robots in dynamic environments.
Finally, Solomon developed a hybrid MRS model with military and industrial applications in which a hierarchical leader-follower approach is implemented in a hybrid central-control and behavior-based control architecture.
Most MRSs possess several common traits, including mobility, intelligence, communications, group behavior and specific functionality.
One critical aspect of robotic group behavior lies less in the value of intelligence that in the importance of methods of aggregation. It is a key challenge of robotic systems of determine ways for robotic agents to synchronize, cooperate and collaborate and, in sum, to work together as a team. The emergence of dynamic coalitions of robotic groups is one of the most interesting and important areas of robotic research.
The effort to achieve the development of complex MRSs that may emulate, and even transcend, emergent natural self-organizing processes, has become primarily a computation challenge that involves the need to create sophisticated AI architectures. AI systems have themselves emulated biological systems, with the advent, from Holland and Koza to the present, of genetic algorithms, genetic programming and evolutionary computation methods in order to solve complex problems. A related research stream involves A-NN, which has utilized GA in order to establish weight values of neural nodes. One main aim of the neural networks is to develop self-configuring and self-organizing learning systems for complex problem solving. This is useful in real time collective robotics situations in which rapid adaptation to a changing environment is necessary.
The development of hybrid AI technologies that synthesize various methods for specified problem solving would provide a robust and successful option in the computer scientist's arsenal of weapons that may be useful for the development of sophisticated MRS architectures.